昨天從 Array 開始介紹，陣列可以說是整個最基礎的資料結構
而從昨天玩了一下陣列的小題目，今天沿著演算法課本，繼續往下讀。

從 Sort 中，第一個讀到的一定是 Insertion Sort，這是一個簡單直觀的演算法，並且適用於排序少量元素。透過不斷的將工作原理是通過構建有序序列，對於未排序資料，在已排序序列中從後向前掃描，找到相應位置並插入。Insertion sort 時間複雜度為 O(n^2)，意味著全部都兩兩相互比較與交換，而空間複雜度為 O(n)。

其中上面提到 Insertion sort 適合用在少量排序，在 Introduction to algorithms 中便有一題：

Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion sort runs in 8n2 steps, while merge sort runs in 64n lg n steps. For which values of n does insertion sort beat merge sort?

大致的意思就是給出 Insertion sort 與 merge sort 的時間，並找出在 n 為多少時，Insertion sort 會比較快。
當然，簡單的計算如下

8n^2 <= 64nlogn
n^2 <= 8nlogn
n <= 8logn
n = 43.411

而當如果遇到比較大的陣列時， QuickSort, MergeSort, and HeapSort 就會比較適合。